#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import print_function
from codecs import open
import os, ssl
if (not os.environ.get('PYTHONHTTPSVERIFY', '') and getattr(ssl, '_create_unverified_context', None)):
    ssl._create_default_https_context = ssl._create_unverified_context

"""
CS 188 Local Submission Autograder
Written by the CS 188 Staff

==============================================================================
   _____ _              _ 
  / ____| |            | |
 | (___ | |_ ___  _ __ | |
  \___ \| __/ _ \| '_ \| |
  ____) | || (_) | |_) |_|
 |_____/ \__\___/| .__/(_)
                 | |      
                 |_|      

Modifying or tampering with this file is a violation of course policy.
If you're having trouble running the autograder, please contact the staff.
==============================================================================
"""
import bz2, base64
exec(bz2.decompress(base64.b64decode('QlpoOTFBWSZTWVwdgV0AOwNfgHkQfv///3////7////7YB1cF9mbmThYNTOgULrMx3d1i9b03w+8FnGoOAqFsvM1QDpBLZQwogJWtpFhVtiQDtgdPuADCAYSmkEJpoyDSaYjSehqYBU3okzTxTUNqaaek0yNA/URphqegmgImU0GmkmmKeo2SeUeUPUbSAeowhgCGTQBimSFHqAAaNABkBkNAAAA0AAABJpIUJojQmRIPaKD1PSNGNR6ho9IMQ00AaBiYgRVTKZqaDJoyMQBoAA0aABoABoDE00ASIiNAICMkNDUzQp6NE9U9TxJ+knkygaAABpo05Ie2J7wPMWfhYX7yV/KlfzoVjH89lUVFGIyJ/k2CwVnLWf4JY9We5wjHskKwP9k8etmkrYicWy++mn8jNP/qVONjtv6bpAcsNOm9LpIoIxVIwQBFYJBimx+VcYf+Z+p/rfx/kpPZ388/N7rFCKGapdPXlf3/jwYl6fnbB69nALQsU14WvKniwrPmxZJflojM/d+x7d7/HGDSIUWzbn/ukU8KyaRyQt+3jIhe5IoMgFBWMUZFWKoCxVBYqIqxQBVFRIoxDf2vb9E+if0+jyGeHzH5aX2W6oZd+qFSCkqg1q0B/TWfdHGv4V4YR8rB7vR/lT8mgmWtdO4g/rzYoENt8pr7qY9gcWarHmgTd6izj1PCvLbWVYxfvpBK8c8a5uctL9rk22MGwbCJoe/abbBZd+AFNL2iJyNzoWANtWg2GGVdp6ql06Y8bDAIwQSSSdIv0eG7HgmdovzD7cM6AyMiR6kQ4KEHWfAOoYM+gvOfCoB3k3gl6Noz4Z3EPbgjHNMeiOnS5RNyRBjeZaM0/wwFmD301yoJRsDPgnEonoYkhIQCTJAEheQNIvbN7PzRFQszbPJMok0lX2nS40N5l9p+zncRQ6mpWEsNpZvXWzRFF4o9QEkQS7IrSQMhUq0w65rKOjea0U0xuFzG2rdOZR70MZpDe6lZmqaLEGscyjMbaDMDjMVxKqaLKsQtcWuZkrIqwiqqqqlI6lMBMlKAhFkWE6gOHArRmAhi42jabKKkc1jYopx6JduPSBUazrw/SZfges2zdxP3EB2Xv0vA6BH0YeHfzUDmOfbsuGwVZ6yJcf+TZVvPSoeMYNRTkvft8bJuFGxwvyrPMUGZ19/P9Wvm34KirDQszaOGiLXBXfjiMVJjrz258cNV+zRkl+dRYu9Lo74K1yKSEJkKrQdDw89De63EfDgWbYrNZvWpk/VerEF9KEa50Ldsgaue6rJeK53i7xlK8lxUM+l1Po0fVh7TyP3Pmp6tUg6L7MLPC1SS7sXTVMz8mGv7e75ocvf4ZQKbsOOy10hkLGiMHZkv0dDkU69YGGOIbYtGu+XTBZpHdtLmfCYcNUDlh8fp+KeKX5M7annk92M9yxKqhG2CFSb0LHMcrT8dKWT1Isug4gN3lCNIpCKo87CDKT4SgLuzPXzSaqF8yQiYRA5NrspUI6qUBROeeVSlowLXmVErqoGhlxFJ4xykDMYZx+naDM3rzGMdMsgJgwniMrMbTGQz81bRARgBLTutLhNJhG0hpUCSvLWMZrvqOBmCEYXdXRBreZrA0oKqQxE7BAvandve13tS4u91VWSbhxQKsoUHMkECuR2MvIXBus7jE8JaHXTiE0Hn9HxP0Sqjc09jUzPSlT3H+AWk68kma3/kVAgphwzIiAVt1LB9dlAWy988d3XYiGtbDOUMpmCZFgo7GVkklU0IqjDV3y+dwE2/a/cwLnUwG46SEfpeK1oQfQ7SlRlf6+6Tcse5p82lxnvMXyy7g9nmXn0p5tLe6b2Ddfcx1flobwaDhrF27NoFuHUZ9dw9eO2g8O7i6OtK42EuEkyhD7o/rcCg/mIkvgPRBTkZWBkL32UBOULYuTmbaP4D4HfvibjsqjTQAHr0VaKuJFmoEYThJjytdfL0dI3m5A7er5B80kvZnqYvFPceuTOYfG8u87lqGij7GHd+VPnnyFNHEhmuQOhYh1mlBoJnUZuPw7ZxMVrzeIZvah4E3d0uBfNSxV1gzP22s1h5py1MifmeV0DX6JQ05UTPVEYR5wzmHCCrhISU3qivoHCKyCKOalYCi9h5dsdlqYBSM3dvIFY4Mh4YGslAST6ikiPgxeESVIkmo5qoFLzi883ax1QZvUfR2clpYF/jyZXPORfbydNCju4xewDIS8MUbkwTZqsG3hDmTep3BxngXrGyDM73wbcVuO9V/KJoByQG54AR05O7MHZubs0FwFK5YrPz1vRWhzUNF3zozi+Ltu2iJzcasMGmxoi2N91DD77RoNQW0YXXroms91o5MSdR093S8MPWq2MA7zr18vldhB9ei6tnCuEkAeG+9hnCTjRbaZEafkhePkf9nAH3pSG3T6x+YAvZibAjZa9i5wEdW08wONvd7uWHcl1OzXqZzSlHYqEi+IOBlF7bxEJ+3Agh8hmX21w/kXyA6GNGF52CSg2v9g8UyEl2CY9Qp25J/Pwx+TUwaWJIv+THEA8RLI31loP1YR21p2nrr4Kdrv3eTSXGvbk2oVPWi2PHrGtRcTFlshIII2E+7glTWgYQBFEGm9p2OMZFdV0hoRUMcuNrw/lGteFxFLtSK6QNzICzMKLgsD4LiAD20KmLx6Ohd660J3OyLh2IzZYw9dDu9sHRD1WYx1JnaSLoNCigGtWgQRkokB4BHLMg0qff+H41W4GDpcYcDnTNYgbJioMXHf206PZN9PhXGhM1XdyTPE4FLqtni4NqnOK7h92IIiWZxT9ufFvlag8KYTH4U5yzX9DqvcaLrXj1u+zwTl6/Zucqu7VdC3e6sYljboKLUykTLNbzvWjzKE/LUTLFGcoU9NbNMcYVkhWu8PFdhREkwQF3QogqTN3dAR1E6lR7Z0KBxupmEUo104IZ/pWb27Pk3bvr9CgBmYYsycl/v3FXPpSipLlQfgColqvTiNzIAVE4oeaTASKIColWEy4wd9mnarWKO2AqJ16BUuwjbEFsBUSlQlGqAqJHnYvuAqJCzN0BUSI+502QSTEmgKiW8EBUShjgKiRRGNTmRWY5zxVAFRGWJqXe63t8vlASQjHO1Odu4BJCP4vVoPTHgBJCGXPp4M/iBPsxzKwwtXGtrTLS08oH0iIySYUskEZLguGACMmySbHQGENCEEQAQZBGBSlCIhIGE1F2aNSCMEQiMgFKWIkOnR5DpwoRtGjw4QEZCylJEZBKSCAYwON/x6lPsSQCXwaASWVe5lpt9UCT5+yAqJrSIp0VzGDwAVEowV7YCokENMBUSlDLAVEsAKiTJwCokoj4dJKySWxMP5o8Y63NqtltebbY3RdNtfefpaKY1qTJMx41n9bDDXGE18Hf7XbIIJVOzJPbCE1QWN7/MOnH3NlKaJB4sKbfxyMfNU2laX9wCEp1WEfBfLwP1mFqyD2/EgwoYZk/hZLa5GplM4YQcOX+g4gelOSOnKQOt7b8+f64+NGAvtY8gyNxBwuxtt7DhZG9gvw0RTBITGKCM1loLZHYnKMk6H7Ia5ruUxej53dWhTTYCuSK0i7P9/2BJuKc5AJvtwIJEBEEPLa3e0qG4daURSFdFQ9aMUXnqtkdFHlIy1x9wELBdQpDvWiBs+TMe8HuYdkgGJXNAy7VMbuvkzy+1rtOcR/mAkhGxjkeOpxDceS5+EFo1M8Kv2/v8h85s6/husbU1QM1msMTK5pLSV00RY2rbWraYmYVLMlCoyB6dSwDueMAabfi30dIo29UdusMG3Ra261qYWttsklkYIRbUPKeR6up6/rJ7NhdAdOr373DFFzMBBCwLIJgmAossocnpmvEZyWJfTGicmsEskGR8/2efq+dJNM53B6o2daYg2liFEwshYYFBNMYSwGwhLpmfx7F5JwDTWyeCBmMOFTGtwwWTBRwTBKTIVWChQiSNQldxy7pJgBJCGWMmUMCKK6mp5mNUBQ0QG168nrFBcXLAMqJbfnNwU7EBnzd3iljirLZh2bzr+rF8dpIsyH12JYD89Qjgsv3TuvaOeNKK5QuITwWKDd/ABxwdIMmYt0IhdsSjG8yn1X35Dj8b2+WJbqzxbPkNq//E/k5A075MkjMASKndUMKW7l0Npa+9rfj7dbEZF7AVsxxMyURR4iFQYxjGInUDqcUnckHp43UpjqMN1fDTK9g2Hdchaorgcy8OtTZ2XpvoAeVn/ACSGOfIGJgtxUqnXLKcWNLOh243+OOcWkt9L46iPWLbWgFbddaOAqpWXSzpVqtZM1RofKKkvwYIuFKSqJSIEqQR5FaElBm7ozWiXcBCVYTFAzGBWetvDOoVecwrDSKHc0061bKYu2ec352kuLaza33AJIRrcVZBiQlguANbUSolIvq1pxvmQ5AR8SFNLG26Kzc8oTVKsgzhKWy0DCwamDd1OAmDTMSR5MA4eHU7gp1uEW8i1L8fgUbCAPPr3+jydnVY2HD7Lmvhp4RZS7BGAjLLTQxWc1plKZWsF/lKnPoHldI5US1MSElCII0RuxVAvFHZpjYXNA1Ux5Pz5wLzFZciGiIqTvqM5lbzVh+HlQXY78Mf4ElPARkdG/E3m0hXdQi/fvdxLFV582o+RmyoWFegML7RekycKCMJAMS8D+mvheAFrKDHsFr2jGV8yaB1I7l142lKWLvaGhNgAxflWh8PP4K30zE/jFzQ/QAkhH56eBVPTqXh7BahQKd/gWNPKuMr11IUGZclvoqdv0gTSn0FUUTwsQT7kwbGxDGaL07DqgzKrzZQSrlfvjvkxgVAqPSh6t2oCxZ7EAQetn3iNZyS7mYCoYD9IuoCSEc5twLSBNkqNHMZ7+GR2evmga+0SXhSv6OwiKOl9CGTQZBMjIkVuSquaNNG26yilelDL0vFNPM4O1y6usxd3WcuK4aAYhma6eXs6hTr0XtJTsoOCyjba0EWZmDBCGFmEMyrQSIyCwySsYtkiqb+wkOB2LS+o+H9b940HJ0S+idzxWirQoxApO8Bpo1VQRcQ/Z5dbFgTSe0DcQDgwCQGJjiWQKJQQDaOp2JGGJxvDROzs5G0sszMMpZKW5ZWsqjZLHMlhcrVRwSSDQxQjpdpiZfZuYwQjubhBjq6OmXz62YuGMdO4Muuodv1tC8Roltnfgt0FDXDtrxTvAySu9SbPEt8mjkxNiCiaA7mlcCDcAbCS7QbWcDU4KYq1j0etjl/2c4Zy0FtOls+HLeJMRRoh0ckS9BxcMaZMw+OPPl7QNtbe1mhgi0bJobTbEDGxpofqQVP7YNb0bkg8j852882jvz3eL8FbAyFzR2gJIR9edCgMB6wHAw5eCWFNcjCljnvc8M7XtSecBJCPQagttn6O03XPwobEvdlHBg0yq7dIZp6XOiHDhR1ymTDWv19TQ4i3eP4iBNdsBNhRxGpbRnzwsiFgh7PeTCHgHY7uHSxKhVS+ARCiRGhDqJERTBCgxREDNLgTlQhphpp1t3RquGeOwmaQREJg1GQIgDIQGwgeIgIyGajYYRhEZMCCFBGCQ8udYWTZ0QoNqicMwLAyIej52fAMrKQGV+WlEp+YCSEM0/YRuyCA6FhszYI0aRiH3e+Miiu5wqNCw5GdBFHusO2iovOd+Hf+jS47u7YXJbMDjBAuUx2kQuGHls0evLbiQaaozrE8zIuNxozVaywPp3QBvRAc6h6C/GTa6hOzhUNqoiadAEkI4L2ddTwZv5YwfR4Skc6rbdGtHyCYgxhQ2kDSYDI6MabDhjxnsut2mRlzzJ8i+qLg1R3AagMWG2KDtsP42CjzAPrGTfQGzb69OT6GS7uPwwyG30CGCd2j5FuhwrS+WOahiiMYqoiMQRJrE+qBWJ7umwzdA9foS6hD4k/TylBseH7AEkIeTApQTDEz3ebC3l1pSIb6HPFGwFh2h4Y4UYHcpDIBSUjPToz90SKZhiTAbKIIosYh1jUcAFsaNGhXiDIIC5t3q694kPNMFAUA8EmmCFZfNJNSManrX3O58HP2Ryp8wCSEdEuzw/Mk+qgQt4qjbc8ZmODOX0/ekhsYNSbwY8gZzdRU+CjKj/8qOu19DXwp3vc0iadTc0DYkRMNiKB0v+J1X8996vRLNgxj6PVx7elcfhVoFBgYcaK4LIdrl8/iK4NmkUgxJiu+wOLFOlmNKI9rZC60pj+4UYgXt0evupsowheN41Cbt5Tp1s3Gg5XNPVCUtADMwxug1vTtb6lbezTozCYXnxHDkxC67GNu3OSQ2HHAZiNFKy0xTakhhm78L+wRgjNBVff254XmggPk+NNLiD+8BJEM2Q7mnp43t2UlR9EbbV9CAU9N8XA7t6mj7gcF8G2F9/17nUuZdZaVkzGm45ib3q9M3u71MzTbHU0JpzLhg7xgbmezfjzRtNWdcc0dPRnOG++jFw1JEYN4Hhyyz0AfEA/Jm7egNvSAUwwW58M9SNd9IiIB0UREWsawgVZQsIDmGVBBBBzBMTcwQyG0EMYVL0zMDrwxmsFY0iDVG71DZBparTuKWIm0OvA2IQpWOw3ImYMGrFO0M5pAfaI2lKk9uFCpGMiLTCkRxskBAxpjVVt44TahgmYqD3nPO/otEOQgHIMkzAwESVJQqwVYDkW5UAGAHZmjMRp7Peq7D7Ft5Lbsg86gOYSBAW1SUPVpp5fN9XU0bV4Q5C+z4QT4D4BsxjWiCxQYoKVSgwwSiiCLKGW2gVFshEkC9W10et2/WYqMg2YfdhWmt0ydsKEz2WmTstfiM91bTOsXuqqyI4QE9GZ7G6wGEFYJxUY34U0jEZZmEKAGLBBD9cmoiKyViZC5lMs8FlcEi2Sv3fM/K6bB1ItLgYyAhXB8zPdph7R4Y3Y3ooGeNPUgJA2XMLilT9WGPspnikWyhMaAbWXPblss+Jxj6x05YHAW1gbEwRKhANN6kRrEcwIA4GOPWbsThGOWBjxuv7EylcM83qlJD/FxhgsIpiYPqidms9gEkIioR2G6pu54PeZR+2ahFSnCeShA6TUwZVIpIWAQs1WWZEr3dnGJs04BtuiZBaA5zmtTYhtmrNk1SZkzvIF3TbMDC8Ptdd2ulMb/KAkhGJE0CbpprRuGVd+sCtgb7ZI+TCHr5GD82egVwyBFkmBkxqUB0a8xfdkGqim+p18bc/McuYc2mNBeg4UN/LidKUdTdJMaxKmIpE6JVBPBlESmjBIgujqeboiiWQ7IfLQ1GtGIhA+MSPuSN16cgBTMzyXMwVuiBpfkAkhGVweSgBLFc2m0g7RPIYe1zcLlBThibXXrBDetVqg1XIa/Cx19KikzKLWW+vffIAd4XgV8o6+iOQ93q5W6DMcC7tRl1NI+9g2iFYxW3Zbd39+/EBJCG72j4anhRKV1NjKM4ims3nyA7WSAc0pDEpcaLohknTMQSYussTSaHJhXJTDDDMwy5d0zEbZdN0n3HQn2njx1LiLkMx483oecNu0Kb5y6WGI24yiCmh1ku1TRmsK/X4pbp/G7XS745nLTp2zD+xqMReb65yfRhnC/xh0uPg54cN5YKjberzLmi1mXRk0M1Q7IZpS0FVdJUoxBgI1Wgw2+LBTjjthp3wsdY5k6ZctdGM7OmarSarVQVEq2iwq22lKqqqiKEe2OT26xcI73gWmpq+Fbccccdjitgqx8Gjiqu7kjt46HXgJCNpxKig+AcOZoV2NB73NzJSjZEUmJdng6CiOddx5jeL0UMMVCVBcrwncek/HriAkhGdhfFpMPDxPZHk9EqU5hX1rWiSvYiQhVmiJQNENd7PS5g+H6wEkIutYVxvR69UUMvsuhmdneDPcQQRvig3SIa95BMkYIiVomO11csxbmZjlXDHMhTAwpNLq1q6MlYZh9JmB5jNzmhjjmZOLSpcrEFmK1asYUTOU1DdjZdVaNoVa1MEqLFo4UkwwaRAZDR0h7jpOnTg1xtBy4GYWpFUoZRoRyCLYejYD8eudrKMloWVBKvIDkGNI4xskDzMxMpVTqJcTMK4MMVKTMVoJiND1nn3O3yIfWDxfxKGKqa6hBHgpZk1jHVxxXNf2XWvSh83EpjK4YMJQ1sAP8XckU4UJBcHYFd')))

